package interview.algorithms.leetcodetop145;

import common.TreeNode;
import common.Util;
import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 2018/5/19 19:58
 */
public class Solution {
    // 遍历二叉树
    public List<Integer> preOrderRecur(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        preOrderRecurCore(root,res);
        return res;
    }
    private void preOrderRecurCore(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preOrderRecurCore(root.left,res);
        preOrderRecurCore(root.right,res);
    }
    public List<Integer> inOrderRecur(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
       inOrderRecur(root.left);
        res.add(root.val);
        inOrderRecur(root.right);
        return res;
    }
    public List<Integer> postOrderRecur(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        preOrderRecur(root.left);
        preOrderRecur(root.right);
        res.add(root.val);
        return res;
    }
    public List<Integer> preOrderUnRecur(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        LinkedList<TreeNode> stack = new LinkedList<>();
        if (root == null) {
            return res;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);

            if (root.right != null) {
                stack.push(root.right);
            }
            if (root.left != null) {
                stack.push(root.left);
            }
        }
        return res;
    }
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (!stack.isEmpty() || root != null) {
            if (root != null){
                stack.push(root);
                root = root.left;
            } else {
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }


    /**
     * 647. Palindromic Substrings
     * @param s
     * @return
     */
    public int countSubstrings(String s) {
        if (s == null || s.length() < 1) {
            return 0;
        }
        int cnt = 0;
        for (int i = 0; i < s.length(); i++) {
            for (int j = i + 1; j <= s.length(); j++) {
                String cur = s.substring(i,j);
                if (isPalindrome(cur,0,cur.length() - 1)) {
                    cnt++;
                }
            }
        }
        return cnt;

    }
    private boolean isPalindrome(String s, int lo, int hi) {
        while (lo < hi) {
            if (s.charAt(lo++) != s.charAt(hi--)) {
                return false;
            }
        }
        return true;
    }

    /**
     * 15. 3Sum
     * @param nums
     * @return
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);
        int n = nums.length;
        for (int i = 0; i < n - 2; i++) {

            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int j = i + 1;
            int k = n - 1;
            int target = -nums[i];
            while (j < k) {
                if (nums[j] + nums[k] == target) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[i]);
                    tmp.add(nums[j]);
                    tmp.add(nums[k]);
                    j++;
                    k--;
                    res.add(tmp);
                    while (j < k && nums[j] == nums[j - 1]) {
                        j++;
                    }
                    while (j < k && nums[k] == nums[k + 1]) {
                        k--;
                    }
                } else if (nums[j] + nums[k] < target) {
                    j++;
                } else {
                    k--;
                }

            }
        }
        return res;
    }

    /**
     * 15
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        backtrackForSubsets(res,new ArrayList<>(), nums,0);
        return res;
    }
    private void backtrackForSubsets(List<List<Integer>> res,List<Integer> tmpLilst, int[] nums,int start) {
        res.add(new ArrayList<>(tmpLilst));
        for (int i = start; i < nums.length; i++) {
            tmpLilst.add(nums[i]);
            backtrackForSubsets(res,tmpLilst,nums,i + 1);
            tmpLilst.remove(tmpLilst.size() - 1);
        }
    }

    /**
     *18. 四数之和
     * bf 去重...
     * @param nums
     * @param target
     * @return
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (nums == null || nums.length < 4) {
            return res;
        }
        Arrays.sort(nums);
        Set<List<Integer>> set = new HashSet<>();
        for (int i = 0; i < nums.length - 3; i++) {
            for (int j = i + 1; j < nums.length - 2; j++) {
                for (int k = j + 1; k < nums.length - 1; k++) {
                    for (int l = k + 1; l < nums.length; l++) {
                        if ((nums[i] + nums[j] + nums[k] + nums[l]) == target) {
                            set.add(Arrays.asList(nums[i],nums[j],nums[k],nums[l]));
                        }
                    }
                }
            }
        }
        return res = new ArrayList<>(set);
    }

    /**
     * 39. 组合总和
     * @param candidates
     * @param target
     * @return
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        if (candidates == null || candidates.length < 1) {
            return res;
        }
        Arrays.sort(candidates);
        backtrackForCombinationSum(candidates,target,0,res,new ArrayList<>());
        return res;
    }
    private void backtrackForCombinationSum(int[] candidates,int remain,int index,List<List<Integer>> res,List<Integer> cur) {
       if (remain < 0 ) {
           return;
       } else if (remain == 0) {
            res.add(new ArrayList<>(cur));
        } else {
           for (int i = index; i < candidates.length; i++) {
               cur.add(candidates[i]);
               backtrackForCombinationSum(candidates, remain - candidates[i], i, res, cur);
               cur.remove(cur.size() - 1);
           }
       }
    }


    public void rotate(int[][] m) {
        int tR = 0;
        int tC = 0;
        int dR = m.length - 1;
        int dC = m[0].length - 1;
        while (tR < dR) {
            rotateEdge(m,tR++,tC++,dR--,dC--);
        }
    }
    private void rotateEdge(int[][] m,int tR, int tC, int dR, int dC) {
        int times = dC - tC;
        int tmp;
        for (int i = 0; i < times; i++) {
            tmp = m[tR][tC + i];
            m[tR][tC + i] = m[dR - i][tC];
            m[dR - i][tC] = m[dR][dC - i];
            m[dR][dC - i] = m[tR + i][dC];
            m[tR + i][dC] = tmp;
        }
    }

    /**
     * 189. 旋转数组
     *
     尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
     要求使用空间复杂度为 O(1) 的原地算法。

     * @param nums
     * @param k
     */
    public void rotate(int[] nums, int k) {
        int len = nums.length;
        k = k % len;
        if (k == 0 || k == len) {
            return;
        }
        reverse(nums,0,len - 1);
        reverse(nums,0,k - 1);
        reverse(nums,k ,len - 1);

    }
    private void reverse(int[] nums,int i,int j) {
        while (i < j) {
            Util.swap(nums,i++,j--);
        }
    }

    /**
     * 442. 数组中重复的数据
     * @param nums
     * @return
     */
    public List<Integer> findDuplicatesI(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length < 2) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] == nums[i + 1]) {
                res.add(nums[i]);
            }
        }
        return res;
    }
    public List<Integer> findDuplicatesII(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length < 2) {
            return res;
        }
        for (int i = 0; i < nums.length; i++) {
           int index = Math.abs(nums[i]) - 1;
           if (nums[index] < 0) {
               res.add(Math.abs(index) + 1);
           }
           nums[index] = -nums[index];
        }
        return res;
    }

    /**
     * 198. 打家劫舍
     * @param nums
     * @return
     */
    public int rob(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        if (nums.length == 2) {
            return Math.max(nums[0],nums[1]);
        }
        int[] dp = new int[nums.length];
        // dp 保存当前最大打劫钱数
        dp[0] = nums[0];
        dp[1] = Math.max(nums[1],dp[0]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1],dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }


    /**
     * 448. 找到所有数组中消失的数字
     * ？？？
     * @param nums
     * @return
     */
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return res;
        }
        for(int i = 0; i < nums.length; i++) {
            int val = Math.abs(nums[i]) - 1;
            if(nums[val] > 0) {
                nums[val] = -nums[val];
            }
        }
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] > 0) {
                 res.add(i+1);
            }
        }
        return res;
    }


    /**
     *4. 两个排序数组的中位数
     * just m+n    没有达到要求 log(m + n);
     * @param nums1
     * @param nums2
     * @return
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] res = merge(nums1,nums2);
        int len = res.length;
        if (len % 2 == 0) {
            return (double)(res[len / 2] + res[len / 2 - 1]) / 2;
        } else {
            return res[len / 2];
        }
    }
    private int[] merge(int[] nums1, int[] nums2) {
        int[] res = new int[nums1.length + nums2.length];
        int i = 0,j = 0,resIndex = 0;
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                res[resIndex++] = nums1[i++];
            } else {
                res[resIndex++] = nums2[j++];
            }
        }
        while (i < nums1.length) {
                res[resIndex++] = nums1[i++];
        }
        while (j < nums2.length) {
                res[resIndex++] = nums2[j++];
        }

        return res;
    }
    /**
     * 11. 盛最多水的容器
     * @param height
     * @return
     */
    public int maxAreaI(int[] height) {
        int max = 0;
        for (int i = 0; i < height.length - 1; i++) {
            for (int j = i + 1; j < height.length; j++) {
                max = Math.max(max,(j - i) * Math.min(height[i],height[j]));
            }
        }
        return max;
    }
    public int maxAreaII(int[] height) {
        int max = 0;
        int lo = 0;
        int hi = height.length - 1;
        while (lo < hi) {
             max = Math.max(max,(hi - lo) * Math.min(height[lo],height[hi]));
            if (height[lo] < height[hi]) {
                lo++;
            } else {
                hi--;
            }
        }
        return max;
    }

    /**
     * 16. 最接近的三数之和
     *              bf?  ...
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        int tmp = Integer.MAX_VALUE;
        int res = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                  if (Math.abs(nums[i] + nums[j] + nums[k] - target) < tmp) {
                      tmp = Math.abs(nums[i] + nums[j] + nums[k] - target);
                      res = nums[i] + nums[j] + nums[k];
                  }
                }
            }
        }
        return res;
    }
    // ohters are good
    public int threeSumClosestII(int[] nums, int target) {
        int n = nums.length;
        int res = nums[0] + nums[1] + nums[n - 1];
        Arrays.sort(nums);
        for (int i = 0; i < n - 2; i++) {
            int st = i + 1;
            int end = n - 1;
            while (st < end) {
                int sum = nums[i]  + nums[st] + nums[end];
                if (sum > target) {
                    end--;
                } else {
                    st++;
                }
                if (Math.abs(sum - target) < Math.abs(res - target)) {
                    res = sum;
                }
            }
        }
        return res;
    }

    /**
     * 26. 删除排序数组中的重复项
     * @param nums
     * @return
     */
    public int removeDuplicatesMine(int[] nums) {
        if (nums == null || nums.length < 1) {
            return 0;
        }
        if (nums.length == 1) {
            return 1;
        }
        int resLen = 1;
        int resIndex = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                nums[resIndex++] = nums[i];
                resLen++;

            } else {
                continue;
            }
        }

        return resLen;
    }
    public int removeDuplicates(int[] nums) {
       int i = 0;
       for (int n : nums) {
           if (i < 1 || n > nums[i - 1]) {
               nums[i++] = n;
           }
       }
       return i;
    }

    /**
     * 80. 删除排序数组中的重复项 II
     * @param nums
     * @return
     */
    public int removeDuplicatesII(int[] nums) {
        int i = 0;
        for (int n : nums) {
            if (i < 2 || n > nums[i - 2]) {
                nums[i++] = n;
            }
        }
        return i;
    }
    @Test
    public void test() {
        int[] nums = {0,0,1,1,1,1,2,3,3};
        int[] nums1 = {1,1,1,2,2,3};
        System.out.println(removeDuplicatesII(nums));
        System.out.println(removeDuplicatesII(nums1));
       /* int[] nums = {-5,5,4,-3,0,0,4,-2};
        List<List<Integer>> res = fourSum(nums,4);
        for (List<Integer> cur : res) {
            for (int i : cur) {
                System.out.print(i + " ");
            }
            System.out.println();
        }*/
      /* int[] candidates = {2,3,6,7};
        List<List<Integer>> res = combinationSum(candidates,7);
        for (List<Integer> cur : res) {
            for (int i : cur) {
                System.out.print(i + " ");
            }
            System.out.println();
        }*/
      /*int[] num = {1,2};
        rotate(num,1);
        for (int i : num) {
            System.out.print(i + " ");
        }*/
        /*int[] num = {4,3,2,7,8,2,3,1};
        findDisappearedNumbers(num);*/
        /*int[] num1 = {2,1,1,2};
        System.out.println(rob(num1));
        int[] num2 = {2,7,9,3,1};
        System.out.println(rob(num2));*/
      /*  int[] nums = {-2, 0, 3, -5, 2, -1};
        NumArray obj = new NumArray(nums);
        System.out.println(obj.sumRange(0,2));
        System.out.println(obj.sumRange(2,5));
        System.out.println(obj.sumRange(0,5));*/
     /*   int[] nums1 = {1, 2};
        int[] nums2 = {3,4};
        System.out.println(findMedianSortedArrays(nums1,nums2));*/
        /*int[] nums1 = {-1,2,1,-4};
        System.out.println(threeSumClosest(nums1,1));*/
       /* int[] nums1 = {1};
        int len = removeDuplicates(nums1);
        System.out.println(len);
        for (int i = 0; i < len; i++) {
            System.out.println(nums1[i] + " ");
        }*/
    }
}

/**
 * 303. 区域和检索 - 数组不可变
 */
class NumArray {
    int[] sum;
    public NumArray(int[] nums) {
        sum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            sum[i + 1] = sum[i] + nums[i];
        }
    }

    public int sumRange(int i, int j) {
        return sum[j + 1] - sum[i];
    }
}
